/*** 
https://leetcode.com/problems/satisfiability-of-equality-equations/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
Intuition:
We have 26 nodes in the graph.
All "==" equations actually represent the connection in the graph.
The connected nodes should be in the same color/union/set.

Then we check all inequations.
Two inequal nodes should be in the different color/union/set.

Explanation
We can solve this problem by DFS or Union Find.

Firt pass all "==" equations.
Union equal letters together
Now we know which letters must equal to the others.

Second pass all "!=" inequations,
Check if there are any contradict happens.

Time Complexity:
Union Find Operation, amortized O(1)
First pass all equations, O(N)
Second pass all inequations, O(N)
Overall O(N)
*/


public boolean equationsPossible(String[] equations) {
        int[] sets = new int[26];
        for(int i=0; i<26; i++) sets[i] = i;
        for(String eq : equations){
            if(eq.charAt(1)=='='){
                int u = find(sets, eq.charAt(0)-'a');
                int v = find(sets, eq.charAt(3)-'a');
                sets[u] = v;
            }
        }
        
        for(String eq : equations){
            if(eq.charAt(1)=='!'){
                int u = find(sets, eq.charAt(0)-'a');
                int v = find(sets, eq.charAt(3)-'a');
                if(u==v) return false;
            }
        }
        return true;
    }
    
    private int find(int[] sets, int v){
        return sets[v]==v ? v : find(sets, sets[sets[v]]); // Path Compression
    }